package leetcode;


import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
import java.util.Stack;

/**
 * 图像渲染
 */
public class LeetCode733 {
    public class Pair {
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Pair)) return false;
            Pair pair = (Pair) o;
            return x == pair.x &&
                    y == pair.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (image.length == 0 || sr >= image.length || sc >= image[0].length) return null;
        int source = image[sr][sc];
        Set<Pair> visited = new HashSet<>();
        Stack<Pair> stack = new Stack<>();
        stack.push(new Pair(sr, sc));
        while (!stack.isEmpty()) {
            Pair pair = stack.pop();
            visited.add(pair);
            if (image[pair.x][pair.y] == source) image[pair.x][pair.y] = newColor;
            if (pair.x - 1 >= 0 && image[pair.x - 1][pair.y] == source && !visited.contains(new Pair(pair.x - 1, pair.y)))
                stack.push(new Pair(pair.x - 1, pair.y));
            if (pair.x + 1 < image.length && image[pair.x + 1][pair.y] == source && !visited.contains(new Pair(pair.x + 1, pair.y)))
                stack.push(new Pair(pair.x + 1, pair.y));
            if (pair.y - 1 >= 0 && image[pair.x][pair.y - 1] == source && !visited.contains(new Pair(pair.x, pair.y - 1)))
                stack.push(new Pair(pair.x, pair.y - 1));
            if (pair.y + 1 < image[0].length && image[pair.x][pair.y + 1] == source && !visited.contains(new Pair(pair.x, pair.y + 1)))
                stack.push(new Pair(pair.x, pair.y + 1));
        }
        return image;
    }

    public static void main(String[] args) {
        int[][] image = new int[][]{{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
        LeetCode733 leetCode733 = new LeetCode733();
        leetCode733.floodFill(image, 1, 1, 2);
    }
}